#include	<stdlib.h>
#include	<string.h>
#include	"typedef.h"
#include	"dlist.h"

struct _DListEntry
{
	struct _DListEntry *next, *prev;
	void *data;
};

struct _DList
{
	struct _DListEntry *head;
	size_t size;
	DataAllocFunc alloc_func;
	DataDestroyFunc destroy_func;
	void *ctxt;
};

void *dlist_entry_value(DListEntry *entry)
{
	return_val_if_fail(entry != NULL, NULL);
	return entry->data;
}

/**
 * @brief	
 *
 * @param	data
 *
 * @return	
 */
static DListEntry *__dlist_create_entry(DList *thiz, void *data)
{
	void *_data;
	DListEntry *entry = (DListEntry *)malloc(sizeof(DListEntry));
	return_val_if_fail(entry != NULL, NULL);

	if (thiz->alloc_func != NULL)
		_data = thiz->alloc_func(thiz->ctxt, thiz->size);
	else
		_data = malloc(thiz->size);

	return_val_if_fail(_data != NULL, NULL);
	memcpy(_data, data, thiz->size);

	entry->data = _data;
	entry->next = entry;
	entry->prev = entry;
	return entry;
}

/**
 * @brief	
 *
 * @param	thiz
 * @param	entry
 */
static void __dlist_destroy_entry(DList *thiz, DListEntry *entry)
{
	return_if_fail(thiz != NULL);
	return_if_fail(entry != NULL);

	if (thiz->destroy_func != NULL)
		thiz->destroy_func(thiz->ctxt, entry->data);
	else
		free_pointer(entry->data);
	free_pointer(entry);
	return;
}

/**
 * @brief	
 *
 * @param	thiz
 * @param	prev
 * @param	next
 *
 * @return	
 */
static void __dlist_add(DListEntry *thiz, DListEntry *prev, DListEntry *next)
{
	thiz->next = next;
	thiz->prev = prev;
	prev->next = thiz;
	next->prev = thiz;
}

/**
 * @brief	
 *
 * @param	prev
 * @param	next
 *
 * @return	
 */
static void __dlist_del(DListEntry *prev, DListEntry *next)
{
	prev->next = next;
	next->prev = prev;
}

/**
 * @brief	
 *
 * @param	destroy_func
 * @param	cmp_func
 * @param	ctxt
 *
 * @return	
 */
DList *dlist_create(size_t size, DataAllocFunc alloc_func, DataDestroyFunc destroy_func, void *ctxt)
{
	DList *list = (DList *)malloc(sizeof(DList));
	return_val_if_fail(list != NULL, NULL);

	list->head = NULL;
	list->size = size;

	if (alloc_func == NULL) {
		alloc_func = __dlist_create_entry;
	}
	list->alloc_func = alloc_func;
	if (destroy_func == NULL) {
		destroy_func = __dlist_destroy_entry;
	}
	list->destroy_func = destroy_func;
	list->ctxt = ctxt;
	return list;
}

/**
 * @brief	
 *
 * @param	thiz
 * @param	ctxt
 *
 * @return	
 */
void dlist_destroy(DList *thiz)
{
	return_if_fail(thiz != NULL);

	while( thiz->head != NULL )
	{
		dlist_del_head(thiz);
	}
	free_pointer(thiz);
}

/**
 * @brief	
 *
 * @param	thiz
 * @param	node
 *
 * @return	
 */
Ret dlist_push_front(DList *thiz, void *data)
{
	DListEntry *entry;
	return_val_if_fail(thiz != NULL, RET_INVALID_PARAM);

	entry = __dlist_create_entry(thiz, data);
	if (thiz->head == NULL) {
		thiz->head = entry;
	}
	else {
		__dlist_add(entry, thiz->head->prev, thiz->head);
		thiz->head = entry;
	}
	return RET_OK;
}

/**
 * @brief	
 *
 * @param	thiz
 * @param	
 * @param	node
 *
 * @return	
 */
Ret dlist_push_back(DList *thiz, void *data)
{
	DListEntry *entry;
	return_val_if_fail(thiz != NULL, RET_INVALID_PARAM);

	entry = __dlist_create_entry(thiz, data);
	if (thiz->head == NULL) {
		thiz->head = entry;
	}
	else {
		__dlist_add(entry, thiz->head->prev, thiz->head);
	}
	return RET_OK;
}

/**
 * @brief	
 *
 * @param	thiz
 * @param	ctxt
 *
 * @return	
 */
Ret dlist_pop_front(DList *thiz)
{
	DListEntry *entry; 
	return_val_if_fail(thiz != NULL, RET_INVALID_PARAM);

	entry = thiz->head;
	return_val_if_fail(entry != NULL, RET_FAIL);

	__dlist_del(entry->prev, entry->next);
	thiz->head = entry->next;
	if (entry->prev == entry && entry == entry->next)
		thiz->head = NULL;
	__dlist_destroy_entry(thiz, entry);
	return RET_OK;
}

/**
 * @brief	
 *
 * @param	thiz
 * @param	node
 * @param	ctxt
 *
 * @return	
 */
Ret dlist_pop_back(DList *thiz)
{
	DListEntry *entry; 
	return_val_if_fail(thiz != NULL, RET_INVALID_PARAM);

	entry = thiz->head;
	return_val_if_fail(entry != NULL, RET_FAIL);

	thiz->head = entry->prev;
	dlist_del_head(thiz);

	return RET_OK;
}

/**
 * @brief	
 *
 * @param	thiz
 * @param	node
 * @param	ctxt
 *
 * @return	
 */
void dlist_remove(DList *thiz, DListIter *iter)
{
	return_if_fail(thiz != NULL && iter != NULL)

	__dlist_del(iter->prev, iter->next);
	__dlist_destroy_entry(thiz, iter);
	return RET_OK;
}

DListIter *dlist_insert(DList *thiz, DListIter *iter, void *data)
{
	DListIter *entry;
	return_if_fail(thiz != NULL && iter != NULL, NULL);

	entry = __dlist_create_entry(thiz, data);
	__dlist_add(entry, iter->prev, iter);

	if (thiz->head == iter) {
		thiz->head = entry;
	}
	return entry;
}

/**
 * @brief	
 *
 * @param	thiz
 * @param	cmp_func
 * @param	ctxt
 *
 * @return	
 */
DListIter *dlist_find(DList *thiz, DListInter *start, DListInter *end, 
		Direct direct, DataCmpFunc cmp_func, void *ctxt)
{
	DListEntry *entry = start;
	return_val_if_fail(thiz != NULL && start != NULL && end != NULL, NULL);

	while (entry != end)
	{
		if (cmp_func(ctxt, entry->data) > 0) break;
		entry = entry->next;
	};

	if (ret) return entry;
	else return NULL;
}

/**
 * @brief	
 *
 * @param	thiz
 * @param	visit_func
 * @param	ctxt
 *
 * @return	
 */
Ret dlist_for_each(DList *thiz, DataVisitFunc visit_func, void *ctxt)
{
	Ret ret;
	DListEntry *entry; 
	return_val_if_fail(thiz != NULL, RET_INVALID_PARAM);

	entry = thiz->head;
	if (entry == NULL) return RET_OK;
	do {
		ret = visit_func(ctxt, entry->data);
		entry = entry->next;
	} while (entry != thiz->head);

	return ret;
}

static Ret __dlist_count(void *thiz, void *data)
{
	(*(int *)thiz)++;
	return RET_OK;
}

size_t dlist_count(DList *thiz)
{
	int i = 0;
	dlist_for_each(thiz, __dlist_count, &i);

	return i;
}

DListEntry *dlist_head(DList *thiz)
{
	DListEntry *entry;
	return_val_if_fail(thiz != NULL, NULL);

	return thiz->head;
}

DListEntry *dlist_tail(DList *thiz)
{
	DListEntry *entry;
	return_val_if_fail(thiz != NULL, NULL);

	if (thiz->head == NULL)
		return NULL;

	entry = thiz->head;
	if (entry->prev == thiz->head)
		return thiz->head;

	return entry->prev;
}

